class KMP():
    @staticmethod
    def indexOf(pattern: str, text: str):
        m = len(pattern)
        n = len(text)
        next = KMP.next(pattern)
        pi, ti = 0, 0
        while pi < m and ti - pi <= n - m:
            if pi < 0 or pattern[pi] == text[ti]:
                ti += 1
                pi += 1
            else:
                pi = next[pi]
        return ti - pi if pi == m else -1

    @staticmethod
    def next(pattern: str) -> []:
        m = len(pattern)
        pi = 0
        next = [0] * m
        preNext = -1
        next[0] = -1
        while pi < m - 1:
            if preNext < 0 or pattern[preNext] == pattern[pi]:
                pi += 1
                preNext += 1
                if pattern[pi] == pattern[preNext]:
                    next[pi] = next[preNext]
                else:
                    next[pi] = preNext
                # next[pi]=preNext
            else:
                preNext = next[preNext]
        return next


if __name__ == '__main__':
    pattern = 'cdefg'
    text = 'abcdefgabcabd'
    result = KMP.indexOf(pattern, text)
    print(result)
